Praktikum 6 - Graafid ja võrgustikud

Sissejuhatus

Tänase praktikumi teema on graafide ja võrgustike visualiseerimine. Seda teeme me kasutades pakette tidygraph ja ggraph. Lisaks kasutamae andmestikku, kus on võetud viimase pooleteise aasta populaarsemad Eesti lood Spotifyst ja nende esitajate kohta tekitatud võrgustik vastavalt sellele kes on omavahel koostööd teinud. Iga artisti kohta on teada tema populaarsus (skaalas 0-100) ja jälgijate arv. Iga serva puhul on kokku loetud koostöös valminud lugude arv ja kõige populaarsema loo populaarsus.

Graafi objekt

Graafi objekti loomine

Graafide jaoks defineerib tidygraph pakett objekti tbl_graph, mis on sisuliselt kaks seotud tibble tüüpi objekti, üks tippude ja teine servade jaoks. Seda defineeritakse käsuga tbl_graph, millele tuleb ette anda kaks tibble või data.frame tüüpi objekti. See käsk ootab, et servade failis oleks kaks veergu: from ja to. Tipu nimed veergudes from ja to peavad olema olemas ka tippude tabelis mingi tunnusena, mille nimi antakse ette argumendiga node_key. Tuleks ka määrata, kas graaf on suunatud või suunamata, argumendiga directed.

edges_est = edges_est %>% 
  rename(from = ArtistName1, to = ArtistName2)

g = tbl_graph(nodes = nodes_est, edges = edges_est, node_key = "ArtistName", directed = F)
g 

Graafe saab luua ka kasutades naabrusmaatrikseid, kasutades paketi igraph fuktsiooni graph.adjacency ja muutes selle tbl_graph objektiks funktsiooniga as_tbl_graph.

library(igraph)

mat = cbind(c(0, 0, 1), c(1, 0, 1), c(1, 0, 0))
rownames(mat) = c("A", "B", "C")
colnames(mat) = c("A", "B", "C")
mat

  A B C
A 0 1 1
B 0 0 0
C 1 1 0

graph.adjacency(mat) %>% 
  as_tbl_graph()

# A tbl_graph: 3 nodes and 4 edges
#
# A directed simple graph with 1 component
#
# Node Data: 3 x 1 (active)
  name 
  <chr>
1 A    
2 B    
3 C    
#
# Edge Data: 4 x 2
   from    to
  <int> <int>
1     1     2
2     1     3
3     3     1
# … with 1 more row

Graafide manipuleerimine

Graafi objekti manipuleerimine tidygraph paketis on väga sarnane tavaliste andmetabelite töötlemisega tidyverse abil. Kuna aga graafi objekt koosneb kahest andmetabelist, siis on lisatud käsk nimega activate, millega saab ette öelda graaf, kas me plaanime rakendada käske tippude või servade tabelile. Vastavalt siis activate(nodes) ja activate(edges) aktiveerivad vastavalt tipud ja servad. Peale seda saame rakendada tuttavaid käske nagu näiteks mutate.

g %>% 
  activate(edges) %>% 
  mutate(VeryPopular = maxPopularity > 40)

g %>% 
  activate(nodes) %>% 
  mutate(VeryPopular = ArtistPopularity > 45)

Kui filtreerida tippusid, siis on sellel tagajärjed ka servadele. Nimelt kustutatakse ära ka servad, mille puhul vähemalt üks tipp andemtest välja visatakse. See on mugav, sest nii ei pea muretsema, et kaks tabelit sünkroonist välja lähevad.

g %>% 
  activate(nodes) %>% 
  mutate(VeryPopular = ArtistPopularity > 45) %>%
  filter(VeryPopular == T)

Erinevate tidyverse funktsioonide kasutamisel on loomulikult piirid. Näiteks summarize on käsk mille käitumist graafil ei ole võimalik üksühele üle kanda ja seega see antud juhul ei tööta. Küll aga töötavad kõik *_join funktsioonid ja on defineeritud graafide liitmine bind_graph abil. Loe lähemalt lingilt https://www.data-imaginist.com/2017/introducing-tidygraph/.

Ülesanded

Loome kaks tabelit

n = tibble(
  Name = c("A", "B", "C", "D"),
  Value = 1:4,
  Class = c("Class1", "Class2", "Class2", "Class2")
)

e = tibble(
  Name1 = c("A", "A", "B", "C", "C", "D"),
  Name2 = c("C", "D", "A", "A", "B", "B")
)

e <- e %>% 
  rename(from = Name1, to = Name2)

tbl_graph$nodes(nodes =e, node_key = )

• Nende tabelite põhjal looge tbl_graph tüüpi objekt. Mõelge, kas antud graaf peaks olema suunatud või suunamata

• Saadud graafist filtreerige välja alamgraaf mis sisaldab ainult klassi “Class2” kuuluvaid tippe.

Graafi joonistamine

Graafe joonistame selles praktikumis paketiga ggraph, mis on sisliselt laiendus ggplot2-le graafi andmete jaoks. Graafik luukase siin käsuga ggraph millele hakatakse siis graafiku elemente liitma. Tippude joonistamiseks on funktsioonid geom_node_* ja servade jaoks geom_edge_*. Andmepunktide kujutused graafilistele parameetritele antekse ette geom_ funktsioonide sees, sest me võime tahta sama parameetrit (näit. värv) defineerida nii tippudele kui servadele.

ggraph(g) +
  geom_node_point() +
  geom_edge_link()

Antud graaf ei näe väga hea välja, sest automaatselt valitud punktide paigutuse algoritm (stress), ei ole optimaalne. Punktide paigutust võib kontrollida parameetriga layout.

Esiteks võib sellele ette anda ühe mitmest paigutus algoritmist, millest mõned on järgnevad:

• “kk” - Kamada and Kawai jõududel põhinev algoritm

• “fr” - Fruchterman and Reingold jõududel põhinev algoritm

• “drl” - järjekordne jõududel põhinev algoritm

• “gem” - järjekordne jõududel põhinev algoritm

• “stress” - järjekordne jõududel põhinev algoritm

• “lgl” - suurtele graafidele sobiv algoritm

• “mds” - kauguste maatrikil dimensiini vähendamiega paigutamine

• “dh” - stohhastilisel lokaalsel otsingul põhinev algoritm

• “nicely” - proovib valida andmetele vastaval hea algoritmi

• “circle” - ringi kujuline paigutus

Paigutuse võib hea tahtmise korral ka ise ette anda maatriksina.

g  

# A tbl_graph: 87 nodes and 74 edges
#
# An undirected simple graph with 34 components
#
# Node Data: 87 x 4 (active)
  ArtistName ArtistPopularity ArtistFollowers ArtistGenre      
  <chr>                 <dbl>           <dbl> <chr>            
1 Pluuto                   42            4231 "estonian hip ho…
2 Nublu                    55           37366 "estonian pop"   
3 5MIINUST                 45           21454 "estonian hip ho…
4 PLUUTO                   25              71 ""               
5 Reket                    48           13520 "estonian hip ho…
6 NOËP                     53           23581 "estonian electr…
# … with 81 more rows
#
# Edge Data: 74 x 4
   from    to nTracks maxPopularity
  <int> <int>   <int>         <dbl>
1    23    24       1            34
2     2    23       1            34
3     3    58       1            44
# … with 71 more rows

lo = cbind(runif(87), runif(87))

lo

             [,1]        [,2]
 [1,] 0.662596733 0.075323027
 [2,] 0.269026553 0.889997697
 [3,] 0.135550009 0.029140577
 [4,] 0.169536707 0.507268359
 [5,] 0.302969098 0.910015675
 [6,] 0.936581166 0.147695661
 [7,] 0.693252315 0.607692787
 [8,] 0.845766872 0.675253721
 [9,] 0.880355598 0.987907342
[10,] 0.029445802 0.368267840
[11,] 0.222628514 0.102911692
[12,] 0.326749816 0.664828027
[13,] 0.009221235 0.447287791
[14,] 0.221918406 0.777034756
[15,] 0.236033614 0.625638479
[16,] 0.877495246 0.927023692
[17,] 0.632426293 0.401834335
[18,] 0.546805055 0.408971063
[19,] 0.411800624 0.607091832
[20,] 0.770410382 0.964285584
[21,] 0.379112357 0.090026133
[22,] 0.546063718 0.107978636
[23,] 0.897821723 0.730566913
[24,] 0.610101395 0.662014036
[25,] 0.351345219 0.975902406
[26,] 0.056662203 0.140464226
[27,] 0.214647673 0.217428566
[28,] 0.022600331 0.571534687
[29,] 0.298666016 0.155996276
[30,] 0.381898565 0.130839787
[31,] 0.638748182 0.524384490
[32,] 0.879089025 0.352608104
[33,] 0.173024775 0.921068273
[34,] 0.898233602 0.923170586
[35,] 0.233122667 0.150494365
[36,] 0.686841902 0.446558392
[37,] 0.981642799 0.758673116
[38,] 0.736455046 0.188965944
[39,] 0.398220531 0.003930629
[40,] 0.919550775 0.290675855
[41,] 0.745733682 0.458774625
[42,] 0.993803212 0.680372039
[43,] 0.704944525 0.612356485
[44,] 0.107252625 0.147779734
[45,] 0.337077885 0.733460389
[46,] 0.615534944 0.626856267
[47,] 0.704329374 0.252769461
[48,] 0.597881675 0.687044830
[49,] 0.229773201 0.644919660
[50,] 0.334824573 0.295184639
[51,] 0.558033166 0.920886023
[52,] 0.519211445 0.876314067
[53,] 0.778482103 0.509269712
[54,] 0.038757446 0.303369572
[55,] 0.650278749 0.747693845
[56,] 0.967808788 0.767233180
[57,] 0.427266140 0.419479232
[58,] 0.851476549 0.829745990
[59,] 0.359234563 0.193245298
[60,] 0.200083146 0.493635337
[61,] 0.354128396 0.410249556
[62,] 0.487300077 0.952217243
[63,] 0.415436797 0.435679120
[64,] 0.624097493 0.108958049
[65,] 0.887584910 0.830717738
[66,] 0.703132574 0.866754119
[67,] 0.735427797 0.755324924
[68,] 0.481408453 0.976971670
[69,] 0.023100206 0.945993355
[70,] 0.776635162 0.965128212
[71,] 0.822792752 0.111939796
[72,] 0.827775015 0.537961433
[73,] 0.340784257 0.639176049
[74,] 0.400972096 0.482579273
[75,] 0.647671234 0.976453587
[76,] 0.674764991 0.923791490
[77,] 0.282198098 0.505036931
[78,] 0.530972903 0.330972680
[79,] 0.549650805 0.694506390
[80,] 0.878241215 0.184076820
[81,] 0.468372708 0.726386093
[82,] 0.075580038 0.654911363
[83,] 0.518065521 0.587482974
[84,] 0.446811819 0.729395255
[85,] 0.531445435 0.857632499
[86,] 0.209030181 0.568405746
[87,] 0.873584309 0.632924577

ggraph(g, layout = lo) +
  geom_node_point() +
  geom_edge_link()

Tippude näitamisel, peale punktide väga häid võimalusi pole. Küll aga on erinevaid võimalusi servade joonistamiseks. Kõige kasutatavam on juba eelpool kasutatud geom_edge_link, mis tõmbab tippude vahele sirged jooned. Teised võimalused on veel:

• geom_edge_arc - teeb kaare punktide vahele

• geom_edge_density - joone asemel teeb kahe punkti vahelist ala natuke tumedamaks, kasulik, kui graaf on väga suur ja tihe

Kui graafid on suunatud saab joontele lisada ka nooli, mida saab spetsifitseerida argumendiga arrow, mis omamkorda võtab väärtuseks arrow funktsiooni grid paketist.

Graafil meta-andmete näitamine

Siiani näidatud graafikud on olnud väga mustvalged ning kohati on raske eristada tippe ja servasid. Värvide ja muude parameetrite lisamine käib sisuliselt sama moodi kui ggplot2-s. Sõltuvalt sellest kas parameeter näitab mõne tunnuse väärtusi või on ilu pärast, läheb ta kas funktsiooni aes sisse või jääb sellest välja. Proovime värvi argumendiga.

#Siin anname lihtsalt värvi tippudele
ggraph(g, layout = "fr") +
  geom_node_point(color = "red") +
  geom_edge_link()

#Siin proovime punktide tumedusega infot edasi anda
ggraph(g, layout = "fr") +
  geom_node_point(aes(color = ArtistPopularity)) +
  geom_edge_link()

Paneme tähele, et jooned tõmmatakse punktide peale, sest nende joonistamise käsk tuli pärast tippude oma. Seetõttu on targem järjekorda muuta.

Peamised parameetrid mida muuta on color, shape (punktidel), size (punktidel), width (joontel) ja linetype (joontel).

Graafiliste parameetrite skaleerimiseks on loodud erandi funktsioonid, et näiteks tippude ja servade värve saaks eraldi skaleerida. Tippude puhul töötavad tavalised scale_* funktsioonid aga servadele on näiteks funktsioonid kujul scale_edge_*. Sellegi poolest töötavad need sama moodi kui tavalised ggplot2 variandid.

Eriti vajalik on skaleerimine serva paksuse kontrollimiseks argumendiga width, mille vaikimisi väärtused on suhteliselt jubedad.

Tekstide lisamine graafile

Siiamaani oleme joonistanud küll punktikesi, kuid nende punktide tegelikku identiteeti võime vaid aimata. Et paremini teada saada, mis tippudega on täpsemalt tegu. saame lisada tippudele nimed. Seda saab teha nii funktsiooniga geom_node_text, kui geom_node_label, mis vastavalt joonistavad lihtsalt teksti või siis kastikesega sildi.

Nüüd on aga probleem, et me ei näe enam tippusid , sest need on tekstide taga peidus. Üleüldse on tekste nii palju, et nad ei mahu hästi ekraanile. Kasulik oleks neid kuidagi vähendada. Üks võimalus on näidata ainult mingis mõttes huvitavamaid tekste, näiteks neid artiste kellel on palju jälgijaid. Selleks saame kasutada geom_* argumenti data, milllele me saame anda ette funktsiooni mis modifitseerib selle kihi andmeid.

Pane tähele, et see funktsioon töötab ainult tippude andmetabelil, sest see on see mille geom_node_label ette saab. Et trükkimise vaeva vähendada saab function(.x){.x %>% filter(ArtistFollowers > 10000)} väljendada lühemalt kui ~ .x %>% filter(ArtistFollowers > 10000). Sellist kuju kasutatakse palju ka tidyverse paketis purrr, mis on mõeldud vektorite ja listide töötlemiseks.

ggraph(g, layout = "fr") +
  geom_edge_link(aes(width = maxPopularity), color = "grey60") +
  geom_node_point(aes(size = ArtistFollowers), color = "darkgreen") +
  scale_edge_width(range = c(0, 2)) +
  geom_node_label(aes(label = ArtistName), data = ~ .x %>% filter(ArtistFollowers > 10000))

Siiski on konkreetsed tipud siltide varjus ja kui silte oleks rohkem, siis kattuksid need ka üle. Et proovida leida siltidele head mitte-ülekattuvad positsioonid võib rakendada argumenti repel, mis proovib optimeerida siltide asukohti.

Lõpuks vaatame graafi kujunduselementide muutmist. Siin töötavad tegelikult kõik ggplot2 theme_*funktsioonid aga kuna neil on suur rühk telgede kujutamisel ning kirjeldamisel, siis graafide jaoks nad liiga head ei ole. Parem on kasutada theme_void või theme_graph. Konkreetsete elementide muutmiseks saab kasutada theme funktsiooni.

Ülesanded

• Proovi saavutada järgmine pilt.

Graafi algoritmid

Graafi struktuurist on võimalik järeldada päris palju huvitavat metainfot, selle info kasutamine võimaldab ka graafe visuaalselt sisukamalt kujutada. Selleks tuleb aga teada kuidas erinevaid graafi algoritme praktikas rakendada.

Kõige lihtsam omadus mille me graaf struktuurist välja saame lugeda on see, kas tipp on ühendatud teiste tippudega või mitte. Selleks on funktsioon node_is_isolated mida saab siis rakendada käskude mutate või filter sees. Pane tähele, et selle käsu töötamiseks peavad olema aktiveeritud tipud. Tippudel on ka palju teisi omadusi mida saab täpsemalt uurida abifailidest ?node_is_isolated.

Järgmisen vaatame tippude seoseid konkreetsete tippudega. Kaugust tippudega saab leida käsuga node_distance_to ja node_distance_from. Suunamata graafi puhul pole suurt vahet kumba kasutada, kuid suunatud graafi puhul tuleb erinevus sisse. Nende käskudega on väga hea eraldada välja alamgraafe, mis keskenduvad ühe punkti ümbrusele. On ka keerukamaid tippude vahelisi suhteid võimalik arvutada ja neid näeb abilehel ?node_distance_to.

Tipu olulisust graafis võib näidata mitut moodi, kuid kõiki neid lähenemisi võetakse kokku ühe terminiga tsentraalsus. Kõig lihtsam tsentraalsuse mõõt, tipu valents, loeb kokku kõik tipu ühendused. Suunatud graafis võib seda teha nii sisse kui väljapoole ühendustega eraldi. R-s saab seda arvutada käsuga centrality_degree. Keerukam tsentraalsusmõõt on betweenness centrality, mis müüdab kui suur osa ühendustest graafi tippude vahel läbib vastavat tippu. Erinevaid algoritme on aga veel (vt ?centrality_degree)

g %>% 
  activate(nodes) %>% 
  mutate(Degree = centrality_degree()) %>% 
  mutate(Centrality = centrality_degree()) %>% 
  ggraph(layout = "kk") + 
    geom_edge_link() + 
    geom_node_point(aes(size = Degree, color = Centrality, alpha = betweenness)) +
    geom_node_label(aes(label = ArtistName), data = ~ .x %>% filter(Centrality > 10))

Error: Aesthetics must be valid data columns. Problematic aesthetic(s): alpha = betweenness. 
Did you mistype the name of a data column or forget to add after_stat()?
Run `rlang::last_error()` to see where the error occurred.

Omadusi võib vaadata ka servadel. Ka nende puhul saab leida servad, mis üheduvad konkreetse tipuga või servasid mis on võrgustikus kesksel kohal. Neid funktsioone saab kasutada käskudega edge_is_from ja centrality_edge_betweenness.

Greefi tippe on ka kasulik klasterdada, et üles leida loogilised alamgraafid. Lihtsaim klasterdamise viis on leida sidusad alamgraafid, mida saab teha käsuga group_components. Keerukamaid kalsterdusi on ka päris palju saadaval ja ühe sellise näiteks võiks olla group_louvain (teiste jaoks uuri ?group_louvain).

g %>% 
  activate(nodes) %>% 
  filter(!node_is_isolated()) %>% 
  mutate(GL = as.factor(group_louvain())) %>% 
  ggraph(layout = "kk") + 
    geom_edge_link() +
    geom_node_point(aes(color = GL))+
  geom_node_label(aes(label = ArtistName), data = ~ .x %>% filter(Centrality > 3))

Error: Problem with `filter()` input `..1`.
x object 'Centrality' not found
ℹ Input `..1` is `Centrality > 3`.
Run `rlang::last_error()` to see where the error occurred.

Ülesanded

• Visualiseeri antud andmestiku kõige suurem sidus komponent. Näita nimedega kõik artistid, kellel on rohkem kui 3 koostööd. Näita punkti tüübiga ära selle selles graafis olevad klastirid (Louvain-i algoritmi järgi)

Kodune ülesanne

Failis spotify_foreign.RData on samasugused andmed aga välisartistide kohta. Proovi sealt välja tuua mõni sinu arvates huvitav seos ühe visualisatsiooniga. Esitada tuleks nii graafi genereeriv kood kui ka selgitus, mida te pildilt välja lugesite. Pildi puhul hindan, milliseid võtteid te olete kasutanud pildi ettevalmistamisel, kasutatud võiks olla vähemalt üks element kõigest järgnevast.

• On leitud sobiv punktide paigutus

• On muudetud tippude graafilisi omadusi

• On muudetud servade graafilisi omadusi

• On näidatud ära huvipakkuvamad tipud nime või mõne muu tekstiga

• On kasutatud graafi algoritme, andmete eeltöötluseks või graafiliste elementide lisamiseks

Lisaks tehnilisele poolele hindan järelduse ja graafiku kokkulangevust ning graafiku visuaalset vormistust.